package com.fallsvc.re.javasesets.mapandset.test;

import javafx.util.Pair;

import java.util.*;

/**
 * @auther falls_vc
 * description:
 * @date 2025/10/27  14:20
 */
public class Demo1 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
//    https://leetcode.cn/problems/copy-list-with-random-pointer/
    // 随机链表的复制

    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>(); /// 存原本节点和复制节点的对应关系
        Node cur = head;
        while(cur != null) {
            Node t = new Node(cur.val);
            map.put(cur,t);
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

//    https://leetcode.cn/problems/jewels-and-stones/submissions/549419214/
//    宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        char[] chs = jewels.toCharArray();
        Set<Character> set = new HashSet<>();
        for(char ch : chs) {
            set.add(ch);
        }

        char[] s = stones.toCharArray();
        int count = 0;
        for(char ch : s) {
            if(set.contains(ch))
                count++;
        }
        return count;
    }

    //https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    // 坏键盘打字
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            String b = in.nextLine();
            printBadKeys(a,b);
        }
    }
    public static void printBadKeys(String aa,String bb) {
        char[] a = aa.toUpperCase().toCharArray();
        char[] b = bb.toUpperCase().toCharArray();
        Set<Character> goodKeys = new HashSet<>();
        Set<Character> badKeys = new HashSet<>();
        for(char ch : b) {
            goodKeys.add(ch);
        }

        StringBuilder stringBuilder = new StringBuilder();
        for(char ch : a) {
            if(!goodKeys.contains(ch)) {
                if(!badKeys.contains(ch)){
                    stringBuilder.append(ch);
                    badKeys.add(ch);
                }
            }
        }

        System.out.println(stringBuilder.toString());
    }

//    https://leetcode.cn/problems/top-k-frequent-words/
//    单词频次

    public List<String> topKFrequent(String[] words, int k) {
        // 1. 记录单词频率
        Map<String,Integer> hash = new HashMap<>();
        for(String str : words) {
            hash.put(str,hash.getOrDefault(str,0) + 1);
        }
        // 2. 建堆
        PriorityQueue<Pair<String,Integer>> p = new PriorityQueue<>(
                (s1,s2) -> {
                    if(s1.getValue().equals(s2.getValue())) {
                        return s2.getKey().compareTo(s1.getKey());
                    }
                    return s1.getValue() - s2.getValue();
                }
        );
        for(Map.Entry<String,Integer> entry : hash.entrySet()) {
            p.offer(new Pair<String,Integer>(entry.getKey(),entry.getValue()));
            if(p.size()>k){
                p.poll();
            }
        }
        // 3. 出堆
        List<String> list = new ArrayList<>();
        while(!p.isEmpty()) {
            list.add(p.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}
